#include "binaryTree.h"
#include "stdlib.h"
#include "logger.h"
SearchTree MakeEmpty(SearchTree T)
{
    if (T)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}
Position Find(ElementType X, SearchTree T)
{
    if (!T)
        return NULL;
    if (T->Element > X)
        return Find(X, T->Left);
    else if (T->Element < X)
        return Find(X, T->Right);
    else
        return T;
}
Position FindMin(SearchTree T)
{
    if (!T)
        return NULL;
    /*
        if (T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
    */
    while (T->Left)
        T = T->Left;
    return T;
}
Position FindMax(SearchTree T)
{
    if (!T)
        return NULL;
    /*
        if (T->Right == NULL)
        return T;
    else
        return FindMax(T->Right);
    */
    while (T->Right)
        T = T->Right;
    return T;
}
SearchTree Insert(ElementType X, SearchTree T)
{
    if (!T)
    {
        T = malloc(sizeof(*T));
        if (!T)
            FatalError("Out of space!");
        T->Element = X;
        T->Left = T->Right = NULL;
        return T;
    }

    if (T->Element > X)
        T->Left = Insert(X, T->Left);
    else if (T->Element < X)
        T->Right = Insert(X, T->Right);

    return T;
}
SearchTree Delete(ElementType X, SearchTree T)
{
    Position Tmp;
    if (!T)
        return NULL;
    if (X < T->Element)
        T->Left = Delete(X, T->Left);
    else if (X > T->Element)
        T->Right = Delete(X, T->Right);
    else if (T->Left && T->Right)
    {
        //将要删除的节点有两个子节点，应该从右子树中找一个最小值替换
        Tmp = FindMin(T->Right);
        //替换当前值
        T->Element = Tmp->Element;
        //实际删除的是替换的节点
        T->Right = Delete(Tmp->Element, T->Right);
    }
    else
    {
        //有一个或者没有子树
        Tmp = T;
        if (T->Left == NULL)
            T = T->Right;
        else if (T->Right == NULL)
            T = T->Left;
        free(Tmp);
    }
    return T;
}
ElementType Retrieve(Position P)
{
    return P->Element;
}
static void Print(SearchTree T, int Depth, int Right)
{
    if (!T)
        return;
    for (int i = 0; i < Depth; i++)
        printf(" ");
    printf("%d:%s\n", T->Element, Right ? "右" : "左");
    Print(T->Left, Depth + 1, 0);
    Print(T->Right, Depth + 1, 1);
}

void PrintTree(SearchTree T)
{
    Print(T, 0, 0);
}
